|
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string searching algorithm created by that uses hashing to find any one of a set of pattern strings in a text. For text of length ''n'' and ''p'' patterns of combined length ''m'', its average and best case running time is O(''n''+''m'') in space O(''p''), but its worst-case time is O(''nm''). In contrast, the Aho–Corasick string matching algorithm has asymptotic worst-time complexity O(''n''+''m'') in space O(''m''). A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical. == Shifting substrings search and competing algorithms == A brute-force substring search algorithm checks all possible positions: function NaiveSearch(string s(), string pattern()) for i from 1 to n-m+1 for j from 1 to m if s() ≠ pattern() jump to next iteration of outer loop return i return not found This algorithm works well in many practical cases, but can exhibit relatively long running times on certain examples, such as searching for a pattern string of 10,000 "a"s followed by a single "b" in a search string of 10 million "a"s, in which case it exhibits its worst-case O(''mn'') time. The Knuth–Morris–Pratt algorithm reduces this to O(''n'') time using precomputation to examine each text character only once; the Boyer–Moore algorithm skips forward not by 1 character, but by as many as possible for the search to succeed, effectively decreasing the number of times we iterate through the outer loop, so that the number of characters examined can be as small as ''n/m'' in the best case. The Rabin–Karp algorithm focuses instead on speeding up lines 3-5. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rabin–Karp algorithm」の詳細全文を読む スポンサード リンク
|